#include <iostream>
#include <vector>

using namespace std;

const int MAX_SIZE = 100;

struct Node
{
    int data;
    int next;
};

class ArrayList
{
private:
    vector<Node> array;
    int head;
    int size;

public:
    ArrayList() : array(MAX_SIZE), head(-1), size(0) {}

    void Push_Back(int data)
    {
        if (size >= MAX_SIZE)
        {
            cout << "链表已满，无法插入新元素！" << endl;
            return;
        }

        int newIndex = size;
        array[newIndex].data = data;
        array[newIndex].next = -1;

        if (head == -1)
        {
            head = newIndex;
        }
        else
        {
            int current = head;
            while (array[current].next != -1)
            {
                current = array[current].next;
            }
            array[current].next = newIndex;
        }
        size++;
    }

    void InsertAfter(int pos, int value)
    {
        if (pos < 0 || pos > size)
        {
            cout << "位置无效，无法插入" << endl;
            return;
        }

        int newIndex = size;
        array[newIndex].data = value;

        if (pos == 0)
        {
            array[newIndex].next = head;
            head = newIndex;
        }
        else
        {
            array[newIndex].next = array[pos - 1].next;
            array[pos - 1].next = newIndex;
        }
        size++;
    }

    void Erase(int value)
    {
        int prev = -1;
        int current = head;

        while (current != -1)
        {
            if (array[current].data == value)
            {
                if (prev == -1)
                {
                    head = array[current].next;
                }
                else
                {
                    array[prev].next = array[current].next;
                }
                size--;
                return;
            }
            prev = current;
            current = array[current].next;
        }
        cout << "未找到要删除的元素" << endl;
    }

    void Search(int value)
    {
        int current = head;
        int count = 0;
        while (current != -1)
        {
            if (array[current].data == value)
            {
                cout << "找到元素 " << value << "，位置为 " << count << endl;
                return;
            }
            current = array[current].next;
            count++;
        }
        cout << "未找到元素 " << value << endl;
    }

    void PrintList()
    {
        int current = head;
        while (current != -1)
        {
            cout << array[current].data << " ";
            current = array[current].next;
        }
        cout << endl;
    }
};

int main()
{
    ArrayList list;
    int data;
    cout << "输入初始化数据:(0结束)" << endl;

    while (cin >> data)
    {
        if (data == 0)
            break;
        list.Push_Back(data);
    }

    bool running = true;
    while (running)
    {
        cout << "请选择相应的操作# 输入首字母即可\t插入insert(pos,value),删除delete(value),查找search(val),遍历traverse(),退出quit" << endl;
        string command;
        cin >> command;

        if (command == "i")
        {
            cout << "请输入位置和数值:" << endl;
            int pos, val;
            cin >> pos >> val;
            list.InsertAfter(pos, val);
        }
        else if (command == "d")
        {
            cout << "请输入要删除的数值:" << endl;
            int val;
            cin >> val;
            list.Erase(val);
        }
        else if (command == "s")
        {
            cout << "请输入要查找的数值:" << endl;
            int val;
            cin >> val;
            list.Search(val);
        }
        else if (command == "t")
        {
            list.PrintList();
        }
        else if (command == "q")
        {
            running = false;
        }
        else
        {
            cout << "无效的命令，请重新输入" << endl;
        }
    }

    return 0;
}